\section{Problema 1}

\subsection{Introducci\'on}
En el primer ejercicio debíamos calcular en qué día comprar y en qué día vender un producto para sacar la mayor ganancia. Recibíamos un arreglo de precios donde cada posición representa un día y debíamos devolver la ganancia máxima obtenible. 

Nuestra solución es sencilla. Simplemente basta con recorrer el arreglo en su totalidad e ir guardando la mejor combinación de días. Luego sólo debemos devolver como resultado final la resta entre el ``mejor máximo'' y el ``mejor mínimo'' que resultaría ser el mayor beneficio posible.

	   
\subsection{Desarrollo}
Nuestro algoritmo siempre recorre la totalidad de los elementos del arreglo de precios que recibimos como entrada. Para resolver el problema guardamos variables que nos indican hasta el momento el día en que el precio fue más bajo, los días en que se compró y vendió para obtener el mayor beneficio y el valor del mayor beneficio obtenido. 

Cada vez que el algoritmo revisa una posición del arreglo de precios verifica si:
\begin{compactenum}
	\item Vendiendo en este día se obtiene una mayor ganancia que la que ya teníamos. Actualiza \textit{MejorVenta} y \textit{Dif} en el pseudocódigo.
	\item Comprando en el mínimo que ya teníamos y vendiendo en este día se obtiene un mayor beneficio. Actualiza \textit{MejorVenta}, \textit{MejorCompra} y \textit{Dif} en el pseudocódigo.
	\item El precio de esta nueva posición es menor que el mínimo obtenido hasta el momento. Actualiza \textit{Min} en el pseudocódigo.
\end{compactenum}
En cada una de estas tres posibilidades se actualizan las distintas variables mencionadas anteriormente.

Notar que el mínimo (\textit{Min}) que vamos guardando es diferente al \textit{MejorCompra} ya que depende de si el mínimo es posterior al \textit{MejorVenta} o no. Sin embargo cada vez que iteramos un día nuevo revisamos si vendiendo en el mínimo encontrado anteriormente y vendiendo en este día es mejor que haber comprado y vendido en los días anteriores; además de las otras cosas que revisa el algoritmo.

Una vez terminado el recorrido del arreglo de precios, se devuelve el beneficio más grande obtenido hasta ese momento.



\subsection{Pseudoc\'odigo}
En el archivo \textbf{Ej1.java} podremos encontrar la clase ``Ej1'' con las funciones para resolver el problema.


\begin{parr}
\begin{algorithm}[H]
\caption{\operL{precios}{ \vin{precios}{int[]}, \vin{n}{int}}{int}} \begin{algorithmic}[1]\parskip=1mm
\STATE \textbf{var} MejorVenta $\leftarrow$ precios[0]
\STATE \textbf{var} MejorCompra $\leftarrow$ precios[0]
\STATE \textbf{var} Dif $\leftarrow$ 0
\STATE \textbf{var} Min $\leftarrow$ precios[0]
\FOR{desde i hasta longitud(precios)}
	\IF{precios[i] $>$ MejorVenta}
		\STATE MejorVenta $\leftarrow$ precios[i]
		\STATE Dif $\leftarrow$ MejorVenta $-$ MejorCompra
	\ENDIF
	\IF{precios[i]-Min $>$ Dif}
		\STATE MejorVenta $\leftarrow$ precios[i]
		\STATE MejorCompra $\leftarrow$ Min
		\STATE Dif $\leftarrow$ MejorVenta $-$ MejorCompra
	\ENDIF	
	\IF{precios[i] $<$ Min}
		\STATE Min $\leftarrow$ precios[i]
	\ENDIF				
\ENDFOR		
\STATE return Dif
\end{algorithmic}
Complejidades:
\begin{compactitem}
	\item líneas 1-4: O(1) (asignaciones)
	\item líneas 6-17 adentro del for: O(1) (asignaciones y guardas en O(1))
	\item for líneas 5-18: $\theta$(cantidad de días)
\end{compactitem}

\end{algorithm}


\end{parr}

\subsection{Demostración de la solución}
Demostraremos ahora por qué el algoritmo nos permite obtener una solución óptima haciendo inducción en la cantidad de elementos del arreglo, o días (la llamaremos \textit{n})
Por inducción en n:

\begin{compactitem}
	\item Caso Base:
	\begin{compactitem}
		\item n = 1: Compro, Vendo y asigno como Mínimo al día 1. Esto hace que el beneficio obtenido sea 0.
		\item n = 2: Tengo 2 elementos [$\alpha$,$\beta$] :
		\begin{compactitem}
			\item En el caso en que $\alpha$ $<$ $\beta$,
			cuando el algoritmo esté iterando el segundo elemento, en el if de la línea 6 asignamos $\beta$ a \textit{MejorVenta}, en el if la línea 10 cambiará la variable \textit{Dif} a $\beta$ menos $\alpha$ y en el tercer if (línea 15) no entrará y quedará $\alpha$ como el mínimo (ya lo habría asignado en la iteración del primero de los dos elementos).
			\item En el caso en que $\alpha$ $=$ $\beta$ en la iteración del segundo elemento no cambiará nada y seguirá siendo $\alpha$ el valor asignado a las 3 variables que fueron asignadas en la primer iteración (o incluso antes, cuando hizo la inicialización antes de entrar al for).
			\item En el caso en que $\alpha$ $>$ $\beta$ cuando itere el primer elemento del arreglo quedará asignado $\alpha$ de nuevo a todas las variables. Cuando itere el segundo no entrara a ningún if y por ende otra vez seguirá siendo $\alpha$ el valor asignado a las 3 variables.
		\end{compactitem}
	\end{compactitem}
	\item Hipótesis Inductiva:Tengo n elementos y tengo hasta el momento un valor de Compra, un valor de Venta y un valor Mínimo con los que se obtiene la solución óptima para esos n elementos.
	\item Paso Inductivo:\\
	Tengo el arreglo de precios [n-1 elementos] con el enésimo elemento concatenado al final.	Puedo aplicar la HI sobre los primeros n-1 elementos y saber cual es el valor obtenido para Comprar, para Vender y como Mínimo. Sólo queda ver que sucede con el n-esimo elemento:
	\begin{compactitem}
		\item Si ahora nos conviene vender en el enésimo día entonces entra al primer if (línea 6) y actualiza las variables \textit{Dif} y \textit{MejorVenta}. Sin embargo, faltaría ver si nos conviene usar el mínimo hasta el momento (recordemos que \textit{MejorCompra} $\neq$ \textit{Min}).
		\item Si conviene vender en el enésimo día como antes y además usa el \textit{Min} como \textit{MejorCompra} entonces entraría al segundo if (línea 10) y modificaría las variables \textit{MejorVenta}, \textit{MejorCompra} y \textit{Dif} con lo que deben valer.
		\item En caso en que el n-ésimo $<$ Mínimo, el tercer if (línea 15) asigna como Mínimo al n-ésimo.
	\end{compactitem}
	Cuando termina la iteración del enésimo elemento tendría modificada la variable Min si el nuevo valor es el mínimo, la variable MejorVenta si el nuevo valor es el mejor nuevo día para vender y si además de este último caso conviene comprar en el día del Min también estaría modificada la variable MejorCompra.
\end{compactitem}



\newpage

\subsection{Complejidad}
La complejidad de este algoritmo es lineal. Esto se debe a que se recorren N elementos de un arreglo y por cada elemento sólo se hacen algunas operaciones básicas que tienen un costo constante. Por lo que podemos afirmar que la complejidad es lineal en la cantidad de elementos del arreglo.

Además, \textbf{siempre} recorrerá los n elementos del arreglo. Ni más ni menos. Por esto, en términos más formales diremos que la complejidad del algoritmo es $ \Theta(n)$, con n igual a la cantidad de elementos del arreglo de precios.


\subsection{Tests}
Vale aclarar que, por lo dicho en la sección de Complejidad, el algoritmo no va a tener un peor caso que haga que la complejidad cambie drásticamente. Debido a esto, decidimos hacer tests con casos que aparenten ser \textit{interesantes} a simple vista:
\begin{compactitem}
	\item Escalera ascendente: los valores van incrementando.
	\item Escalera descendente: los valores van decrementando.
	\item Todos iguales.
	\item Valores random.
\end{compactitem}

\subsection{Gr\'aficos}

\begin{figure}[H]
\centering
\epsfig{file=./graficos/Ej1/todos-juntos-png.pdf,width=0.9\linewidth,clip=}
\caption{Tests para números ascendentes, descendentes, random y todos iguales.}
\end{figure}

Como se ve en el gráfico, podemos acotar por arriba y por abajo las ejecuciones del algoritmo con funciones lineales. Además, podemos notar que hay una diferencia de crecimiento constante entre los diferentes tests con el test de números ascendentes creciendo más rápido que los demás y el test de todos iguales creciendo más lento que los demás. Aunque la diferencia sea constante, nos parece \textit{interesante} remarcar a qué se debe esto.

Si miramos con atención el pseudocódigo veremos que en el caso del test \textit{ascendente} siempre \textit{entrará} a ejecutar las instrucciones de los primeros 2 \textbf{ifs} (líneas 6-9 y 10-14) porque cada día nuevo es el mejor día para vender, y nunca entraría al último \textbf{if} después del primer día. En el caso del \textit{descendente} sería al revés: se metería en los primeros 2 \textbf{ifs} sólo en la iteración del primer día y siempre se metería en el tercer if en los días restantes ya que siempre irán descendiendo los precios por lo que siempre tendrá que actualizar el mínimo.

En el caso de \textit{todos iguales}, se meterá en los ifs sólo al principio pero después siempre darán false las guardas de éstos. Sólo nos queda analizar el test \textit{random} pero es claro: algunas veces se meterá en los \textbf{ifs} y otras veces no, lo que explicaría su fluctuación de valores en el gráfico.

En todo caso, la diferencia es constante porque las operaciones de adentro de los ifs son de tiempo constante.

\subsection{Conclusiones}
Como conclusión podemos decir que resolvimos el ejercicio cumpliendo la complejidad pedida por el enunciado y consideramos que es simple y fácil de comprender. En los tests no encontramos sorpresas y pudimos graficar y analizar sin problemas y encontramos una correlación entre lo previsto mirando el pseudocódigo y los resultados empíricos obtenidos.

